/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let m = board.length, n = board[0].length
  let ans = false
  const directions = [{ x: 0, y: 1 }, { x: 0, y: -1 }, { x: 1, y: 0 }, { x: -1, y: 0 }]
  const visited = new Array(m).fill().map(() => new Array(n).fill(false))
  const dfs = (x, y, count) => {
    if(count == word.length - 1) {
      ans = true
      return
    }
    visited[x][y] = true
    for (let i = 0; i < directions.length; i++) {
      let x1 = x + directions[i].x
      let y1 = y + directions[i].y
      if (valid(x1, y1, count + 1, m, n, word, board, visited)) {
        dfs(x1, y1, count+1)
      }
    }
    visited[x][y] = false
    count--
  }
  for(let i = 0; i < m; i++) {
    for(let j = 0; j < n; j++) {
      if(board[i][j] === word[0] && !visited[i][j]) {
        dfs(i, j, 0)
      }
    }
  }
  return ans
};
function valid(x, y, count, m, n, word, grid, visited) {
  return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] === word[count] && !visited[x][y]
}
console.log(exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], 'ABCCED'));
console.log(exist([['a']], 'b'));